﻿// 3691. 有向树形态.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <memory.h>

using namespace std;
/*
https://www.acwing.com/problem/content/3694/

求 N个结点能够组成的二叉树的个数。

输入格式
一个整数 N。

输出格式
输出能组成的二叉树的个数。

数据范围
1≤N≤20
输入样例：
3
输出样例：
5
*/

const int N = 22;
long long  dp[N];
int n;

long long dpfunc(int x) {
	if (dp[x] != -1) return dp[x];
	long long& v = dp[x];
	v = 0;

	for (int i = 0; i < x; i++) {
		v += dpfunc(i) * dpfunc(x - 1 - i);
	}

	return v;
}


int main()
{
	cin >> n;
	memset(dp, -1, sizeof dp);
	dp[0] = 1; dp[1] = 1; dp[2] = 2;
	cout << dpfunc(n) << endl;

	return 0;
}

